package cn.suchan.jianzhi.sort;

/**
 * 快速排序
 *
 * @author suchan
 * @date 2019/06/18
 */
public class QuickSort {

    public void sort(int[] array, int start, int end) {
        if (start > end) {
            return;
        }
        int i = start;
        int j = end;
        int k = array[i];
        while (i < j) {
            // 一定是j先移动
            // 找到小于k的元素
            while (i < j && array[j] > k) {
                j--;
            }
            // 找到大于k的元素
            while (i < j && array[i] <= k) {
                i++;
            }
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        // 写明白点可以这样写
        /*
        k = array[i];
        int temp = array[i];
        array[i] = array[start];
        array[start] = temp;
         */
        k = array[i];
        array[i] = array[start];
        array[start] = k;

        sort(array, start, i - 1);
        sort(array, i + 1, end);

    }

    public static void main(String[] args) {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        QuickSort sort = new QuickSort();
        sort.sort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.printf(array[i] + " ");
        }
    }
}
